package com.fyl.leetcode.sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author:fyl
 * @date 2021/4/27 9:40
 * @Modified By:
 * @Modified Date:
 * @Description: 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
 *
 * 把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
 */
public class TopKFrequentElements {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freForNum = new HashMap<>();
        //将数组的各个数字频率存入freForNum中
        for (int num : nums) {
            freForNum.put(num, freForNum.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        //遍历所有key值，将数据放入桶中
        for (int key : freForNum.keySet()) {
            int frequency = freForNum.get(key);
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(key);
        }

        List<Integer> topK = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
            if (buckets[i] == null) {
                continue;
            }
            topK.addAll(buckets[i]);

//            if (buckets[i].size() < (k - topK.size())) {
//                topK.addAll(buckets[i]);
//            } else {
//                topK.addAll(buckets[i].subList(0, k - topK.size()));
//            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = topK.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] num = {1,1,1,2,2,3} ;
        int[] topKFrequent = TopKFrequentElements.topKFrequent(num, 2);
        System.out.println(topKFrequent);
    }
}
